package com.chuci.Algo;


import java.util.Arrays;
import java.util.Random;

/**
 * 这段程序接受一个白名单文件（一列整数）
 * 作为参数，并会过滤掉标准输入中的所有存在
 * 于白名单中的条目，仅将不在白名单上的整数
 * 打印到标准输出中。它在 rank() 静态方法中实
 * 现了二分查找算法并高效地完成了这个任务。
 */
public class BinarySearch {


    public static void main(String[] args) {
        final int LEN = 1000;
        Random random = new Random();
        random.setSeed(10);
        int[] arrs = new int[LEN];
        for (int i = 0; i < LEN; i++) {
            arrs[i] = random.nextInt(1000);
        }
        System.out.println("排序前：" + Arrays.toString(arrs));

        Arrays.sort(arrs);

        System.out.println("排序后：" + Arrays.toString(arrs));


        int key = 29;
        int res = rank(key, arrs);
        if (res == -1) {
            System.out.println(key + "不存在于数组~");
        } else {
            System.out.println("存在于排序数据的：" + (res + 1) + "位");
        }

    }

    public static int rank(int key, int[] arr) {
//        定义指针指向数组的最低端
        int lo = 0;
//        定义指针指向数据的最高端
        int hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (key < arr[mid]) {
                hi = mid - 1;
            } else if (key > arr[mid]) {
                lo = mid + 1;
            } else return mid;
        }
        return -1;
    }
}
